﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Net;
using System.Runtime.InteropServices;
using System.Text;
using System.Threading.Tasks;

// 归并排序
// 测试链接 : https://www.luogu.com.cn/problem/P1177

namespace ZuoAlgorithms.Class021;
public class Code01_MergeSort
{
    public static int MAXN = 100001;

    public static int[] arr = new int[MAXN];

    public static int[] help = new int[MAXN];

    public static int n;


    // 归并排序递归版
    // 假设l...r一共n个数
    // T(n) = 2 * T(n/2) + O(n)
    // a = 2, b = 2, c = 1
    // 根据master公式，时间复杂度O(n * logn)
    // 空间复杂度O(n)
    public static void MergeSort1(int l, int r)
    {
        if (l == r)
            return;
        int m = (l + r) / 2;
        MergeSort1(l, m);
        MergeSort1(m + 1, r);
        Merge(l, m, r);
    }


    // 归并排序非递归版
    // 时间复杂度O(n * logn)
    // 空间复杂度O(n)
    public static void MergeSort2()
    {
        // 一共发生O(logn)次
        for (int l, m, r, step = 1; step < n; step <<= 1)
        {
            // 内部分组merge，时间复杂度O(0)
            l = 0;
            while (l < n)
            {
                m = l + step - 1;
                if (m + 1 >= n)
                {
                    break;
                }
                r = Math.Min(l + (step << 1) - 1, n - 1);
                Merge(l, m, r);
                l = r + 1;
            }
        }
    }

    // l....r 一共有n个数
    // O(n)
    public static void Merge(int l, int m, int r)
    {
        int i = l;
        int a = l;
        int b = m + 1;
        while (a <= m && b <= r)
        {
            help[i++] = arr[a] <= arr[b] ? arr[a++] : arr[b++];
        }
        // 左侧指针、右侧指针，必有一个越界，另一个不越界
        while (a <= m)
        {
            help[i++] = arr[a++];
        }
        while (b <= r)
        {
            help[i++] = arr[b++];
        }
        for (i = l; i <= r; i++)
        {
            arr[i] = help[i];
        }
    }

}
